import java.util.Arrays;
import java.util.Random;


public class MergeSort {

	public static void main(String[] args){
		//int[] vals = {34,3,5,6,7,3,8,9,0,0,2,3,4,1,34,223,1,44,521};
		//int[] vals = {256, 128, 64, 32, 16, 8, 4, 2, 1};
		int[] bigVals = new int[10];
		for(int i = 0; i < 10; ++i){
			bigVals[i] = (new Random()).nextInt() % 100;
		}
		//mergesort(vals, 0, vals.length-1);
		//System.out.println(Arrays.toString(vals));
		System.out.println(Arrays.toString(bigVals));
		mergesort(bigVals, 0, 9);
		System.out.println(Arrays.toString(bigVals));
		
		System.out.println(Quicksort.checkArray(bigVals));
	}

	public static void mergesort(int[] elements, int left, int right){
		if(left < right){
			int split = (left + right)/2;
			mergesort(elements, left, split);
			mergesort(elements, split+1, right);
			merge(elements, left, right, split+1);
		}
	}
	public static void merge(int[] elements, int left, int right, int split){
		int l = left;
		int s = split;
		int[] scratch = new int[right - left+1];
		for(int i = 0; i < scratch.length; ++i){
			if(left < s && split > right  || elements[left] <= elements[split]){
				scratch[i] = elements[left];
				left++;
			}
			else{
				scratch[i] = elements[split];
				split++;
			}
		}
		for(int i = l; i <= right; ++i){
			elements[i] = scratch[i - l];
		}
	}
}
